Search Results

Documents authored by Tan, Zihan

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.37
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics

Authors: Yu Chen, Sanjeev Khanna, and Zihan Tan

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We consider the design of sublinear space and query complexity algorithms for estimating the cost of a minimum spanning tree (MST) and the cost of a minimum traveling salesman (TSP) tour in a metric on n points. We start by exploring this estimation task in the regime of o(n) space, when the input is presented as a stream of all binom(n,2) entries of the metric in an arbitrary order (a metric stream). For any α ≥ 2, we show that both MST and TSP cost can be α-approximated using Õ(n/α) space, and moreover, Ω(n/α²) space is necessary for this task. We further show that even if the streaming algorithm is allowed p passes over a metric stream, it still requires Ω̃(√{n/α p²}) space. We next consider the well-studied semi-streaming regime. In this regime, it is straightforward to compute MST cost exactly even in the case where the input stream only contains the edges of a weighted graph that induce the underlying metric (a graph stream), and the main challenging problem is to estimate TSP cost to within a factor that is strictly better than 2. We show that in graph streams, for any ε > 0, any one-pass (2-ε)-approximation of TSP cost requires Ω(ε² n²) space. On the other hand, we show that there is an Õ(n) space two-pass algorithm that approximates the TSP cost to within a factor of 1.96. Finally, we consider the query complexity of estimating metric TSP cost to within a factor that is strictly better than 2 when the algorithm is given access to an n × n matrix that specifies pairwise distances between n points. The problem of MST cost estimation in this model is well-understood and a (1+ε)-approximation is achievable by Õ(n/ε^{O(1)}) queries. However, for estimating TSP cost, it is known that an analogous result requires Ω(n²) queries even for (1,2)-TSP, and for general metrics, no algorithm that achieves a better than 2-approximation with o(n²) queries is known. We make progress on this task by designing an algorithm that performs Õ(n^{1.5}) distance queries and achieves a strictly better than 2-approximation when either the metric is known to contain a spanning tree supported on weight-1 edges or the algorithm is given access to a minimum spanning tree of the graph. Prior to our work, such results were only known for the special cases of graphic TSP and (1,2)-TSP. In terms of techniques, our algorithms for metric TSP cost estimation in both streaming and query settings rely on estimating the cover advantage which intuitively measures the cost needed to turn an MST into an Eulerian graph. One of our main algorithmic contributions is to show that this quantity can be meaningfully estimated by a sublinear number of queries in the query model. On one hand, the fact that a metric stream reveals pairwise distances for all pairs of vertices provably helps algorithmically. On the other hand, it also seems to render useless techniques for proving space lower bounds via reductions from well-known hard communication problems. Our main technical contribution in lower bounds is to identify and characterize the communication complexity of new problems that can serve as canonical starting point for proving metric stream lower bounds.
Cite as

Yu Chen, Sanjeev Khanna, and Zihan Tan. Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2023.37,
  author =	{Chen, Yu and Khanna, Sanjeev and Tan, Zihan},
  title =	{{Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.37},
  URN =		{urn:nbn:de:0030-drops-180892},
  doi =		{10.4230/LIPIcs.ICALP.2023.37},
  annote =	{Keywords: Minimum spanning tree, travelling salesman problem, streaming algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.38
A New Conjecture on Hardness of 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems

Authors: Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, and Zihan Tan

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We propose a new conjecture on hardness of 2-CSP’s, and show that new hardness of approximation results for Densest k-Subgraph and several other problems, including a graph partitioning problem, and a variation of the Graph Crossing Number problem, follow from this conjecture. The conjecture can be viewed as occupying a middle ground between the d-to-1 conjecture, and hardness results for 2-CSP’s that can be obtained via standard techniques, such as Parallel Repetition combined with standard 2-prover protocols for the 3SAT problem. We hope that this work will motivate further exploration of hardness of 2-CSP’s in the regimes arising from the conjecture. We believe that a positive resolution of the conjecture will provide a good starting point for other hardness of approximation proofs. Another contribution of our work is proving that the problems that we consider are roughly equivalent from the approximation perspective. Some of these problems arose in previous work, from which it appeared that they may be related to each other. We formalize this relationship in this work.
Cite as

Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, and Zihan Tan. A New Conjecture on Hardness of 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 38:1-38:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chuzhoy_et_al:LIPIcs.ITCS.2023.38,
  author =	{Chuzhoy, Julia and Dalirrooyfard, Mina and Grinberg, Vadim and Tan, Zihan},
  title =	{{A New Conjecture on Hardness of 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{38:1--38:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.38},
  URN =		{urn:nbn:de:0030-drops-175411},
  doi =		{10.4230/LIPIcs.ITCS.2023.38},
  annote =	{Keywords: Hardness of Approximation, Densest k-Subgraph}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.33
On Packing Low-Diameter Spanning Trees

Authors: Julia Chuzhoy, Merav Parter, and Zihan Tan

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Edge connectivity of a graph is one of the most fundamental graph-theoretic concepts. The celebrated tree packing theorem of Tutte and Nash-Williams from 1961 states that every k-edge connected graph G contains a collection 𝒯 of ⌊k/2⌋ edge-disjoint spanning trees, that we refer to as a tree packing; the diameter of the tree packing 𝒯 is the largest diameter of any tree in 𝒯. A desirable property of a tree packing for leveraging the high connectivity of a graph in distributed communication networks, is that its diameter is low. Yet, despite extensive research in this area, it is still unclear how to compute a tree packing of a low-diameter graph G, whose diameter is sublinear in |V(G)|, or, alternatively, how to show that such a packing does not exist. In this paper, we provide first non-trivial upper and lower bounds on the diameter of tree packing. We start by showing that, for every k-edge connected n-vertex graph G of diameter D, there is a tree packing 𝒯 containing Ω(k) trees, of diameter O((101k log n)^D), with edge-congestion at most 2. Karger’s edge sampling technique demonstrates that, if G is a k-edge connected graph, and G[p] is a subgraph of G obtained by sampling each edge of G independently with probability p = Θ(log n/k), then with high probability G[p] is connected. We extend this result to show that the diameter of G[p] is bounded by O(k^(D(D+1)/2)) with high probability. This immediately gives a tree packing of Ω(k/log n) edge-disjoint trees of diameter at most O(k^(D(D+1)/2)). We also show that these two results are nearly tight for graphs with a small diameter: we show that there are k-edge connected graphs of diameter 2D, such that any packing of k/α trees with edge-congestion η contains at least one tree of diameter Ω((k/(2α η D))^D), for any k,α and η. Additionally, we show that if, for every pair u,v of vertices of a given graph G, there is a collection of k edge-disjoint paths connecting u to v, of length at most D each, then we can efficiently compute a tree packing of size k, diameter O(D log n), and edge-congestion O(log n). Finally, we provide several applications of low-diameter tree packing in the distributed settings of network optimization and secure computation.
Cite as

Julia Chuzhoy, Merav Parter, and Zihan Tan. On Packing Low-Diameter Spanning Trees. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chuzhoy_et_al:LIPIcs.ICALP.2020.33,
  author =	{Chuzhoy, Julia and Parter, Merav and Tan, Zihan},
  title =	{{On Packing Low-Diameter Spanning Trees}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{33:1--33:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.33},
  URN =		{urn:nbn:de:0030-drops-124405},
  doi =		{10.4230/LIPIcs.ICALP.2020.33},
  annote =	{Keywords: Spanning tree, packing, edge-connectivity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact